#include<iostream>
#include<vector>
using namespace std;
/*
给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
解题思路1：
dp[i][j]表示的是要使s中以下标i-1为结尾和t中以下标j-1为结尾的字符串相同的最少删除操作的次数
当s中下标i-1与t中下标j-1相同时，与之前的状态进行类比，i-2与j-2下标时的操作次数相同所以
dp[i][j] = dp[i-1][j-1]
当s中下标i-1与t中下标j-1不同时，可以删除s中下标i-1让t与i-1之前的进行比较，也可以不改变s与t的j-1之前元素进行比较
也可以同时删除s与t中的i-1与j-1然后让他们与之前的两个进行比较,删除操作的次数需要加上
所以有dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+2))
根据dp数组的含义进行初始化
dp[i][0]表示的是使s以下标为i-1结尾和t中以-1结尾的元素相同的最少删除操作的次数
所以为i次
同理dp[0][j] = j

解题思路2：
该题目在删除s与t中的元素使其变为相同之后，相同的元素是s与t的最长公共子序列，所以我们可以将该题转化为求最长公共子序列的问题
求出最长公共子序列之后让结果为s.size()+t.size()-2*result;
*/
int dp(string word1,string word2)
{
    //创建dp数组
    vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
    //初始化
    for(int i=0;i<=word1.size();i++)
        dp[i][0] = i;
    for(int j=0;j<=word2.size();j++)
        dp[0][j] = j;
    //遍历dp数组
    for(int i=1;i<=word1.size();i++)
    {
        for(int j=1;j<=word2.size();j++)
        {
            if(word1[i-1]==word2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+2));
        }
    }
    return dp[word1.size()][word2.size()];
}
int dp2(string word1,string word2)
{
    //创建dp数组
    vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
    for(int i=1;i<=word1.size();i++)
    {
        for(int j=1;j<=word2.size();j++)
        {
            if(word1[i-1]==word2[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
    //由于dp[i][j]表示的是s中以i-1和t中以j-1为下标的最长公共子序列
    //那么返回的结果应该是s中下标最大元素为结尾和t中下标最大元素为结尾的最长公共子序列长度
    return word1.size()+word2.size()-2*dp[word1.size()][word2.size()];
}
int main()
{
    cout<<"enter word1:"<<endl;
    string word1;
    cin>>word1;
    cout<<"enter word2:"<<endl;
    string word2;
    cin>>word2;
    cout<<dp(word1,word2);
    return 0;
}